package test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ans {
    // 暴力破解法
    public int[] twoSumBruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // 哈希表法
    public int[] twoSumHashTable(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // 双指针法
    public int[] twoSumTwoPointers(int[] nums, int target) {
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);
        int left = 0;
        int right = sortedNums.length - 1;
        while (left < right) {
            int sum = sortedNums[left] + sortedNums[right];
            if (sum == target) {
                int index1 = findIndex(nums, sortedNums[left]);
                int index2 = findIndex(nums, sortedNums[right]);
                if (index1 != index2) {
                    return new int[]{index1, index2};
                } else {
                    index2 = findIndex(nums, sortedNums[right], index1);
                    return new int[]{index1, index2};
                }
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    private int findIndex(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    private int findIndex(int[] nums, int target, int excludeIndex) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target && i != excludeIndex) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入数组的长度: ");
        int n = scanner.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数组的元素:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        System.out.print("请输入目标值: ");
        int target = scanner.nextInt();
        scanner.close();

        ans ans = new ans();
        int[] resultBruteForce = ans.twoSumBruteForce(nums, target);
        int[] resultHashTable = ans.twoSumHashTable(nums, target);
        int[] resultTwoPointers = ans.twoSumTwoPointers(nums, target);

        System.out.println("暴力破解法的结果: " + Arrays.toString(resultBruteForce));
        System.out.println("哈希表法的结果: " + Arrays.toString(resultHashTable));
        System.out.println("双指针法的结果: " + Arrays.toString(resultTwoPointers));
    }
}
